package th.retrofit.lib;

/**
 * https://leetcode-cn.com/problems/reverse-linked-list-ii/
 * 给你单链表的头指针 head 和两个整数left 和 right ，其中left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */
public class Solution92 {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) return head;
        right = right - left;
        ListNode start = head;
        ListNode pre = null;
        while (left > 1) {
            pre = start;
            start = start.next;
            left--;
        }
        ListNode tail = start;
        while (right > 0) {
            tail = tail.next;
            right--;
        }
        ListNode temp = tail;
        tail = tail.next;
        temp.next = null;
        ListNode newHead = reverse(start);
        if (pre != null) {
            pre.next = newHead;
            pre = head;
        } else {
            pre = newHead;
        }
        start.next = tail;
        return pre;
    }

    private ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }


    public static void main(String[] args) {
        ListNode head = ListNode.arr2Node(1, 2, 3, 4, 5);
        System.out.println(new Solution92().reverseBetween(head, 3, 4));
    }
}
